package LeetCode.leetcode131;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

class Solution {
    public List<List<String>> partition(String s) {
        List<List<String>> res = new ArrayList<>();
        List<String> answer = new ArrayList<>();
        backTracking(res,answer,0,s);
        return res;
    }
    public static void backTracking(List<List<String>> res,List<String> answer,int startIndex,String s){
        if (startIndex == s.length()){
            res.add(new ArrayList<>(answer));
            return;
        }
        for (int i = startIndex; i < s.length(); i++) {
            if (checkValid(s,startIndex,i+1)){
                String tmp = s.substring(startIndex,i+1);
                answer.add(tmp);
                backTracking(res,answer,i+1,s);
                answer.remove(answer.size()-1);
            }
        }
    }
    public static boolean checkValid(String s,int left, int right){
        int l = left;
        int r = right-1;
        while (l <= r){
            if (s.charAt(l++) != s.charAt(r--))
                return false;
        }
        return true;
    }
}
